package com.peng.leetcode.tree;

/**
 * Rob1
 * 337. 打家劫舍 III
 * https://leetcode.cn/problems/house-robber-iii/
 * <p>
 * Created on 2022/12/2
 *
 * @author lupeng
 */
public class Rob1 {

    public int rob(TreeNode root) {
        int[] a = dfs(root);
        return Math.max(a[0], a[1]);
    }

    int[] dfs(TreeNode n) {
        if (n == null) {
            return new int[]{0, 0};
        }
        int[] l = dfs(n.left);
        int[] r = dfs(n.right);
        // 偷根节点
        int t = n.val + l[1] + r[1];
        // 不偷
        int nt = Math.max(l[0], l[1]) +  Math.max(r[0], r[1]);
        return new int[]{t, nt};
    }
}
